package com.lwt.codetop.arrayOrSort;

// 33. 搜索旋转排序数组

/**
 * 寻找target位置
 * 思路：二分：原有序数组旋转后生成的两段 各自是有序的
 *          首先第一次二分定位tar在哪一段就要先划分出两段， 即找到两段的分界点：二分判断的依据是nums[0]，第一段都是>nums[0]的，第二段都是<nums[0]的
 *          确定tar位于哪一段后，第二次二分找到tar所在的位置
 */
public class SearchInRotatedSortedArray {
    public static void main(String[] args) {
        // 构建测试用例
        int[] nums = {4,5,6,7,0,1,2};
        int target = 0;
        // 搜索
        int res = search(nums, target);
        System.out.println(res);
    }

    /**
     * 两次二分，找出tar在旋转数组中的位置
     * @param nums
     * @param target
     * @return
     */
    private static int search(int[] nums, int target) {
        int n = nums.length;
        //第一次二分： 找出两段划分的分界点
        int l = 0, r = n - 1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }
        if(l > r) return -1;
        // 判断tar位于哪一段
        if(target >= nums[0]){
            l = 0;
        }else{
            l = r + 1;
            r = n - 1;
        }
        //第二次二分：找出tar的位置
        while (l < r){
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if(l <= r && nums[l] == target) return  l;

        return -1;
    }
}
